package Solution101_200;

import java.util.List;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/18 22:00
 */
public class Solution120Triangle {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null||triangle.size()==0){
            return 0;
        }
        int[] resultArray=new int[triangle.size()];
        for(int i=0;i<triangle.size();i++){
            List<Integer> level=triangle.get(i);
            for(int j=level.size()-1;j>=0;j--){
                if(j==0){
                    resultArray[j]=level.get(j)+resultArray[j];
                }else if(j==level.size()-1){
                    resultArray[j]=level.get(j)+resultArray[j-1];
                }else {
                    resultArray[j]=level.get(j)+Math.min(resultArray[j],resultArray[j-1]);
                }
            }
        }

        int result=resultArray[0];
        for(int i=1;i<resultArray.length;i++){
            if(resultArray[i]<result){
                result=resultArray[i];
            }
        }
        return result;
    }
}
